/*
 HOJA DE TRABAJO 5 b
Colaheaps.java
Fecha: 2 de septiembre 2011
Autora: Claudia Grajeda
Descripcion: Inteface de la cola. Usando java collection Framework 
*/

import java.util.Vector;




public class ColaHeaps<E> implements IntefaceHeaps<E>{

	public Vector<E> data; // the data, kept in heap order
	public ColaHeaps()
	// post: constructs a new priority queue
	{
	data = new Vector<E>();
	}
	
	public ColaHeaps(Vector<E> v)
	// post: constructs a new priority queue from an unordered vector
	{
	int i;
	data = new Vector<E>(v.size()); // we know ultimate size
	for (i = 0; i < v.size(); i++)
	{ // add elements to heap
	add(v.get(i));
	}
	}
	
	public int parent(int i)
	// pre: 0 <= i < size
	// post: returns parent of node at location i
	{
	return (i-1)/2;
	}
	
	public int left(int i)
	// pre: 0 <= i < size
	// post: returns index of left child of node at location i
	{
	return 2*i+1;
	}
	
	public int right(int i)
	// pre: 0 <= i < size
	// post: returns index of right child of node at location i
	{
	return 2*(i+1);
	}
	
	public void percolateUp(int leaf)
	// pre: 0 <= leaf < size
	// post: moves node at index leaf up to appropriate position
	{
	int parent = parent(leaf);
	E value = data.get(leaf);
	
	data.set(leaf,data.get(parent));
	leaf = parent;
	parent = parent(leaf);
	
	data.set(leaf,value);
	}
	
	
	public void add(E value)
	// pre: value is non-null comparable
	// post: value is added to priority queue
	{
	data.add(value);
	percolateUp(data.size()-1);
	}
}